package com.leet.grapth;

public class FindRedundantConnect {
    public int find(int[] parent,int index){
        if(parent[index] != index){
            parent[index] = find(parent, parent[index]);
        }
        return parent[index];
    }
    public void union(int[] parent,int index1,int index2){
        // 2的父亲设置成1的父亲，设置成公共祖先
        parent[find(parent,index1)] = find(parent,index2);
    }
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        int[] parent = new int[n+1];
        // 初始化最初的父亲
        for(int i = 0 ; i < parent.length; i++){
            parent[i] = i;
        }
        for(int i = 0 ; i < n; i++){
            // 取第几行，用数组接着,并查集从边入手
            int[] edge = edges[i];
            if(find(parent,edge[0])!=find(parent,edge[1])){
                union(parent,edge[0],edge[1]);
            }
            else return edge;
        }
        return new int[0];
    }
}
